Introduction

Bipartite graphs are graphs that have two (bi-) partitions (-partite) of nodes. Nodes within each partition are not allowed to be connected to one another; rather, they can only be connected to nodes in the other partition.

Bipartite graphs can be useful for modelling relations between two sets of entities. We will explore the construction and analysis of bipartite graphs here.

Class Exercise

Earlier on in class, I had asked you to write down a list of cities for which you had visited. Now, I would like you to go about creating the bipartite graph of people & cities in the class. You may wish to get up from your seats to finish this last task.



In [1]:

    
import networkx as nx
from networkx.algorithms import bipartite



In [2]:

    
# Initialize the city/person bipartite graph.
B = nx.Graph()

cities = ['Beijing', "Xi'an", 'Vancouver', 'San Francisco', 'Austin', 'Boston'] # populate a list of cities
people = ['Eric', 'Nan'] # populate a list of people's names 

B.add_nodes_from(cities, bipartite='cities')
B.add_nodes_from(people, bipartite='people')

edges = [("Eric", "Vancouver"), ("Nan", "Xi'an"), ("Eric", "San Francisco"), ("Nan", 'Boston'), ("Eric", 'Boston'), ("Nan", 'Beijing')] # populate a list of 2-tuples, which are the edges. Each 2-tuple should join one city with one person. 
B.add_edges_from(edges)

Explore the graph by going through the following algorithms



In [3]:

    
# Betweenness Centrality
bipartite.betweenness_centrality(B, cities)









    Out[3]:





{'Austin': 0.0,
 'Beijing': 0.0,
 'Boston': 0.75,
 'Eric': 0.45,
 'Nan': 0.45,
 'San Francisco': 0.0,
 'Vancouver': 0.0,
 "Xi'an": 0.0}



In [4]:

    
# Degree Centrality
bipartite.degree_centrality(B, cities)









    Out[4]:





{'Austin': 0.0,
 'Beijing': 0.5,
 'Boston': 1.0,
 'Eric': 0.5,
 'Nan': 0.5,
 'San Francisco': 0.5,
 'Vancouver': 0.5,
 "Xi'an": 0.5}

Think about it...

Which metric is the better indicator of city popularity? How about how well-travelled an individual is?

Projection to a uni-partite graph

A bipartite graph can be projected down to a unipartite graph. The projection joins nodes of the same partition, based on their connections to nodes in the other partition. For example, if A is joined to 1 and B is joined to 1, then A and B will be joined in the uni-partite graph projection.

Exercise

Use the bipartite.projected_graph(G, nodes) function to construct the 'people' uni-partite projection.

Hint: bipartite.projected_graph(G, nodes) returns a NetworkX Graph or MultiGraph (with multiple edges between nodes).



In [5]:

    
bipartite.projected_graph(B, people).edges()









    Out[5]:





[('Nan', 'Eric')]

Cities connect people in unique ways. :) In the graph, those who you are connected to are people you can talk with about cities you've been to before, and hopefully it'll kick off some networking.

Think about it...

How would you construct a bipartite graph for the Divvy bike sharing data set?

Exercise

Give it a shot below.



In [ ]: